#include<iostream>
using namespace std;
#include<algorithm>
//void insert_sort(int* a, int n)
//{
//	for (int i = 1; i < n; i++)
//	{
//		int tmp = a[i], end = i - 1;
//		while (end >= 0)
//		{
//			if (a[end] < tmp)
//			{
//				a[end + 1] = a[end];
//				end--;
//			}
//			else
//			{
//				break;
//			}
//		}
//		a[end + 1] = tmp;
//	}
//}
//
//void shell_sort(int* a, int n)
//{
//	int gap =n;
//	while (gap > 1)
//	{
//		gap /= 2;
//		for (int i = gap; i < n; i++)
//		{
//			int end = i - gap;
//			int tmp = a[end + gap];
//			while (end >= 0)
//			{
//				if (a[end] > tmp)
//				{
//					a[end + gap] = a[end];
//					end -= gap;
//				}
//				else break;
//			}
//			a[end + gap] = tmp;
//		}	
//	}
//}
//void shell_sort(int* a, int n)
//{
//	int gap = n;
//	while (gap>1)
//	{
//		gap /= 2; 
//		for (int i = gap; i < n; i++)
//		{
//			int end = i - gap;
//			int tmp = a[end+gap];
//			while (end >= 0)
//			{
//				if (a[end] > tmp)
//				{
//					a[end+gap] = a[end];
//					end -= gap;
//				}
//				else break;
//			}
//			a[end + gap] = tmp;
//		}
//	}
//}
//
void select_sort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int mini = left, maxi = left;
		for (int i = left + 1; i <= right; i++)
		{
			if (a[i] < a[mini])mini = i;
			if (a[i] > a[maxi])maxi = i;
		}
		swap(a[left], a[mini]);
		if (left == maxi)maxi = mini;
		swap(a[right], a[maxi]);
		left++;
		right--;
	}
}

//void bubble_sort(int* a, int n)
//{
//	for (int i = 0; i < n - 1; i++)
//	{
//		int cnt = 0;
//		for (int j = 0; j < n - i - 1; j++)
//		{
//			if (a[j] > a[j + 1])
//			{
//				cnt++;
//				swap(a[j], a[j + 1]);
//			}
//		}
//		if (cnt == 0)break;
//	}
//}

void down(int* a, int x, int n)
{
	int y = x *2 +1;
	while (y < n)
	{
		if (y + 1 < n && a[y + 1] > a[y])y++;
		if (a[x] < a[y])
		{
			swap(a[x], a[y]);
			x = y;
			y = x * 2 + 1;
		}
		else break;
	}
}

void heap_sort(int* a, int n)
{
	for (int i = (n - 2) / 2; i >= 0; i--)down(a,i,n);
	
	int end = n - 1;
	while (end)
	{
		swap(a[0], a[end]);
		down(a, 0, end);
		end--;
	}
}

void test()
{
	int arr[] = { 8,6,7,5,3,4,2,0 };
	//insert_sort(arr, 8);
	//shell_sort(arr, 8);
	//select_sort(arr, 8);
	//sort(arr, arr + 8);
	//bubble_sort(arr, 8);
	heap_sort(arr, 8);
	for (int i = 0; i < 8; i++)cout << arr[i] << ' ';
}

int main()
{
	test();
	return 0;
}